/*
BUG1：输入没有做为空check
BUG2：如果数组有重复项，需要过滤掉
BUG3：算法超时，时间复杂度不够：设计是每次插入点都是在小于自己的节点的后面，构建链表，然后再遍历该链表，计算连续数字的个数，这种方式个问题：
    一碰到小于自己就插入，起始并没有完全按照顺序插入，应该是同时满足前面比自己小，后面比自己大才能够插入
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "framework/hashtable/uthash.h"

typedef struct lnode
{
    int val;
    struct lnode *next;
} link_node;

void insertNode(int val, link_node *head);
int longestConsecutive(int *nums, int numsSize);

void insertNode(int val, link_node *head)
{
    printf("###insertNode::val: %d\n", val);
    link_node *new_node = (link_node *)malloc(sizeof(link_node));
    new_node->val = val;
    new_node->next = NULL;

    if (head->next == NULL)
    {
        printf("value(%d) is HEAD\n", val);
        head->next = new_node;
    }
    else
    {
        link_node *preview_node = head;
        int insert_flag = 0;
        while (preview_node->next != NULL)
        {
            link_node *current_node = preview_node->next;
            int current_node_val = current_node->val;
            // 如果当前val值
            if (val < current_node_val)
            {
                preview_node->next = new_node;
                new_node->next = current_node;
                insert_flag = 1;

                printf("INSERT LINK::preview value: %d; new value: %d; current value: %d\n", preview_node->val, new_node->val, current_node->val);
                break;
            }

            preview_node = current_node;
        }
        // 遍历链表节点没有则将该节点添加到末尾
        if (0 == insert_flag)
        {
            preview_node->next = new_node;
        }
    }
}

int longestConsecutive(int *nums, int numsSize)
{
    // BUG1: 没有考虑入参为空场景
    if (numsSize == 0)
    {
        return 0;
    }

    link_node *head = (link_node *)malloc(sizeof(link_node));
    head->next = NULL;
    // 按照从大到小的顺序构建一个链表
    for (int i = 0; i < numsSize; i++)
    {
        insertNode(*(nums + i), head);
    }

    link_node *preview_node = head;
    int index = 0;
    printf("after build link, print link data:\n");
    while (preview_node->next != NULL)
    {
        link_node *current_node = preview_node->next;
        printf("link index: %d,  value: %d\n", index, current_node->val);
        index++;
        preview_node = current_node;
    }

    // 遍历链表, 查找最大连续数据
    preview_node = head->next;
    int counter = 1;
    int max_counter = 0;
    int preview_val = preview_node->val;
    while (preview_node->next != NULL)
    {
        link_node *current_node = preview_node->next;
        int current_val = current_node->val;
        // BUG2 需要考虑数组中存在相等值的情况，如果不处理，相等值也会参与计数
        if (current_val == preview_val)
        {
            printf("The value is same, just skip\n");
        }
        else if (1 == (current_val - preview_val))
        {
            counter++;
            printf("Continus, counter+1! preview_val: %d; current_val: %d; counter is: %d\n", preview_val, current_val, counter);
        }
        else
        {
            printf("NO Continus(current_val: %d, preview_val: %d), counter clear! max_counter: %d; counter: %d\n",
                   current_val, preview_val, max_counter, counter);
            if (counter > max_counter)
            {
                printf("old max counter: %d, new_max_counter: %d\n", max_counter, counter);
                max_counter = counter;
            }
            else
            {
                // do nothong
            }

            counter = 1;
            printf("recounter, counter reset: %d\n", counter);
        }

        preview_node = current_node;
        preview_val = current_node->val;
    }

    max_counter = max_counter > counter ? max_counter : counter;

    return max_counter;
}

void main(void)
{
    // int nums[] = {100, 4, 200, 1, 3, 2};
    // int nums[] = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
    int nums[] = {1, 2, 0, 1};
    int num_count = sizeof(nums) / sizeof(int);
    printf("num_count: %d\n", num_count);
    int max_counter = longestConsecutive(nums, num_count);

    printf("max_count: %d\n", max_counter);
}